﻿#include <iostream>

#define INT_SIZE sizeof(int)
#define MAX(a, b) (a > b ? a : b)
#define MINIMUM_NUMBER -0x1ffffff

static int maxForOneLine(const int* arr, size_t arrSize)
{
    int max = MINIMUM_NUMBER;
    int cur = 0;
    for (int i = 0; i < arrSize; i++)
    {
        cur += arr[i];
        max = MAX(max, cur);
        if (cur < 0)
        {
            cur = 0;
        }
    }

    return max;
}

/**
 * 给定一个整形矩阵，返回子矩阵的最大累计和。
 *
 * 思路：
 * 1. 假设矩阵共有n行，则需要考虑：
 * 0->0, 0->1, 0->2,...,0->n;
 * 1->1, 1->2, 1->3,...,1->n;
 * 2->2, 2->3, 2->4,...,2->n;
 * ...
 * (n-1)->(n-1),(n-1)->n
 * 这些范围的所有子矩阵的情况。
 *
 * 2. 某个子矩阵的各个元素的最大累计和，可以将每一列的数字压缩到一个数字上，即
 *
 *   a b c
 * [ d e f ]
 *   g h i
 *
 * 可以组成一个数组: [a+d+g, b+e+h, c+f+i], 然后利用 class MaxOfLengthOfContinuousNumbers 中的方法，
 * 求得最大的连续的局部和，即为这个矩阵的最大累计和.
 */
int main_MaxSummationOfSubMatrix()
{
    int colSize = 5;
    int matrix[] = {
        5, -1, 0, 2, 3,
        7, 2, 0, -5, -3,
        -9, 9, 9, 12, 15,
        -15, -16, 8, 20, 1
    };

    int rowSize = sizeof(matrix) / (colSize * INT_SIZE);

    int* lineArr = (int*)malloc(colSize * INT_SIZE);
    memset(lineArr, 0, colSize * INT_SIZE);
    int maxNumber = MINIMUM_NUMBER;
    for (int y = 0; y < rowSize; y++)
    {
        memcpy(lineArr, matrix + y * colSize, colSize * INT_SIZE);

        for (int y1 = y; y1 < rowSize; y1++)
        {
            if (y1 > y)
            {
                for (int x = 0; x < colSize; x++)
                {
                    lineArr[x] += matrix[x + y1 * colSize];
                }
            }
			
            auto maxOneLine = maxForOneLine(lineArr, colSize);
            maxNumber = MAX(maxNumber, maxOneLine);
        }
    }
	
    printf("%d\n", maxNumber);
    free(lineArr);

    return 0;
}